package fun.coding.leetcode;

import java.util.ArrayList;
import java.util.List;

public class BSTIterator {

	public static void main(String[] args) {

	}
	
	// This uses O(N) memory, so it is easy
	private List<Integer> a = new ArrayList<Integer>();
	private int index = 0;
	
	public BSTIterator(TreeNode root) {
		this.index = 0;
		this.inorder(root);
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return this.index < a.size(); 
    }

    /** @return the next smallest number */
    public int next() {
        return a.get(this.index++);
    }

    private void inorder(TreeNode root) {
    	if (root == null) return;
    	
    	inorder(root.left);
    	this.a.add(root.val);
    	inorder(root.right);
    }
}
